package dynamicprograming;

import java.util.HashMap;
import java.util.Map;

public class CoinChange {
    public static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static int coinChange(int[] coins,int amount){
        if (map.containsKey(amount)) return map.get(amount);

        if (amount==0) return 0;
        if (amount<0 || coins.length==0) return -1;
        int res=amount+1;
        for (int coin:coins){
            int subproblem=coinChange(coins,amount-coin);
            if (subproblem<0) continue;
            res=Math.min(res,subproblem+1);
        }
        map.put(amount,res);
        return res;
    }

    public static void main(String[] args) {
        int coins[]= {1,2,5};
        int amout=0;
        System.out.println(coinChange(coins,amout));
    }
}
